package leetcode_1601_1700;

import java.util.*;

public class LeeCode_1654 {
    public static void main(String[] args) {
        System.out.println(minimumJumps(new int[]{8, 3, 1, 6, 16, 20}, 15, 17, 9));
        System.out.println(minimumJumps(new int[]{14, 4, 18, 1, 15}, 3, 15, 9));

        System.out.println(minimumJumps(new int[]{8,3,16,6,12,20}, 15, 13, 11));
    }
    private static int minimumJumps(int[] forbidden, int a, int b, int x) {
        boolean[] vis = new boolean[6001];
        int n = vis.length;
        for (int i : forbidden) {
            vis[i] = true;
        }
        Deque<int[]> queue = new ArrayDeque<>();
        int step = 0;
        queue.add(new int[]{0, 1});
        while (!queue.isEmpty()){
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] p = queue.pop();
                if (p[0] == x)
                    return step;
                if (p[0] < 0 || p[0] >= n || vis[p[0]]){
                    continue;
                }
                if (p[1] == 1){
                    vis[p[0]] = true;
                }
                queue.add(new int[]{p[0] + a, 1});
                if (p[1] == 1){
                    queue.add(new int[]{p[0] - b, -1});
                }
            }
            step++;
        }
        return -1;
    }
}
